﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace KongZhiTaiTest.AlgorithmAndStruct
{
    /// <summary>
    /// 快速排序
    /// 1. 入参：数组本身、左指针、右指针
    /// 第一步：找到基准值并将数组中所有比基准值小的数据放在基准值的左侧，将比基准值大的数据放在基准值的右侧。
    /// 2. 选定基础：将数组最左侧的元素当作基础数据，并定义两个指针(i,j);
    /// 3. 从右边开始循环寻找比基准值小的数据，直到找打为止；然后开始从左边开始循环寻找直到找到比基准值大的数值为止。
    /// 4. 交换上边这两个值。
    /// 5. 继续【3，4】步骤，直到两个指针i，j相遇为止，然后交换基础值和当前指针所指向的数值。
    /// 第二步：此时基准值两侧分别为比基础值大或比基础值小的两部分，然后分别针对左侧部分以及右侧部分进行排序，步骤与【2，3，4，5】一致。
    /// 6. 先对左边进行排序，完成之后再对右边进行排序。
    /// 7. 完成所有步骤。
    /// </summary>
    class QuickSort
    {
        public static void Show()
        {
            int[] arr = new int[10];
            var r = new Random();
            for (int i = 0; i < arr.Length; i++)
            {
                arr[i] = r.Next(100);
            }
            QuickSortAlg(arr, 0, arr.Length - 1);
            foreach (var item in arr)
            {
                Console.Write(item + "  ");
            }
        }

        public static void QuickSortAlg(int[] arr,int leftIndex,int rightIndex)
        {
            if (rightIndex < leftIndex) return;
            int baseNum = arr[leftIndex];
            int i = leftIndex;
            int j = rightIndex;
            while (i != j)
            {
                //先从右边开始循环检索，直到发现比基础数据小的数据
                while(arr[j]>baseNum&& j > i)
                {
                    j--;
                }
                //再从左边开始循环检索，直到发现比基础数据大的数据
                while (arr[i] < baseNum && i < j)
                {
                    i++;
                }
                if (i == j) break;
                //交换位置
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;

            }
            //两个指针一旦相遇，则完成一次完整排序，需要交换基础数据和当前指针所指位置值。
            arr[leftIndex] = arr[i];
            arr[i] = baseNum;
            //从此步开始，将数组进行分割
            //先排左边，递归调用此排序方法
            QuickSortAlg(arr, leftIndex, i - 1);
            //再排右边剩余部分数组
            QuickSortAlg(arr, j + 1, rightIndex);

        }
    }
}
